package someTestExcemple.huaweiOd.dp.dp01;
//华为OD机试 - 最多获得的短信条数 - 动态规划（Java 2023 B卷 100分）
//https://blog.csdn.net/guorui_java/article/details/131927867
import java.util.*;
//典型的完全背包问题
//完全背包问题的特点是每种物品可以选择无限次，
public class MaxMessageNum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取客户预算
        int M = Integer.parseInt(scanner.nextLine());
        // 读取售价表
        String[] priceStr = scanner.nextLine().split(" ");
        int n = priceStr.length;
        int[] prices = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prices[i + 1] = Integer.parseInt(priceStr[i]); //表示充值i元获取的短信条数
        }
        // 动态规划数组
        int[] dp = new int[M + 1]; //dp[j] 表示预算为 j 时最多可获得的短信条数。
        // 填充动态规划数组
        for (int i = 1; i <= n; i++) {
            //没必要从0开始遍历，因为小于i的预算都无法购买
            for (int j = i; j <= M; j++) {
                //计算充补充j元的获得广告条数最大值
                dp[j] = Math.max(dp[j], dp[j - i] + prices[i]);
            }
        }

        // 输出最多获得的短信条数
        System.out.println(dp[M]);
        scanner.close();
    }
}
